Data processors, for example microprocessors and digital signal processors, are commonly called upon to perform many multiplication operations each second. Consequently, data processors often include one or more multipliers in order to perform such operations efficiently.
Multiplication is often carried out by (1) generating partial products, and (2) summing the partial products. As to generating partial products, two different techniques are commonly used. The first technique uses 2-input AND gates. The second technique uses booth encoding. Compared to the 2-input AND gates method, the booth encoding method results in fewer partial products. Because there are fewer partial products, fewer summing operations are needed to generate the product.
A multiplier that uses booth encoding techniques is referred to herein as a booth-encoded multiplier. FIG. 1 shows an example of a booth-encoded multiplier 20. The booth-encoded multiplier 20 is made up of a booth-encoded partial product generator unit 22 and an adder 24. The partial product generator unit 22 receives a multiplicand A and a multiplier B. The multiplicand A is received through an operand bus 32. The multiplier B is received through an operand bus 34.
The multiplicand A and the multiplier B are typically each multi-bit digital signals. For example, the multiplicand may have bits an-1, an-2, . . . a1, a0, where bit an-1 is the most significant bit (MSB) and bit a0 is the least significant bit (LSB). The multiplier B may have bits bn-1, bn-2, . . . b1, b0, where bit bn-1 is the MSB and bit b0 is the LSB. There is no requirement for the multiplicand A to have the same number of bits as the multiplier B.
The partial product generator unit 22 generates m partial products, PP0–PPm-1. Each of the partial products is a multi-bit digital signal. For example, the partial product PP0 may have bits PP0k-1, PP0k-2, . . . PP01, PP00, where bit PP0k-1 is the MSB and bit PP00 is the LSB. Likewise for the partial products PP1–PPm-1. For example, the partial product PPm-1 may have bits PPm-1k-1 . . . PPm-10, where bit PPm-1k-1 is the MSB and bit PPm-10 is the LSB.
The partial products PP0–PPm-1 are supplied to the adder 24. It should be understood that the adder 24 is also supplied with sign bits, which are generated from the multiplier B directly, but which are not shown. The adder 24 determines the sum, which is indicative of the product of the multiplicand A and the multiplier B. The adder 24 outputs the result, i.e., Product, on a data bus 48. It should also be understood that the adder is typically made-up of a partial product compression tree (e.g., made up of carry save adders) and a fast two operand adder (e.g., such as a carry look ahead adder), which are not shown.
FIG. 2 shows a block diagram of one prior art implementation of the booth-encoded partial product generator unit 22 (FIG. 1). The prior art partial product generator unit 22 includes m partial product generators, four of which are shown, i.e., 60A, 60B, 60C and 60D. The m partial product generators are all identical to one another. Each partial product generator has inputs A, bj+1, bj, bj−1, and an output, PPj. The A input of each of the partial product generators receives the multiplicand A. The bj+1, bj, bj−1 inputs receive groups of bits of the multiplier B. The PPj output of each partial product generator supplies one of the partial products. More specifically, the partial product generator 60A receives the multiplicand A and multiplier bits b1, b0 (input bj−1 is supplied with 0, i.e., a signal having a logic low state), and supplies the partial product PP0. The partial product generator 60B receives the multiplicand A and bits b3, b2, b1 of the multiplier B, and supplies the partial product PP1. The partial product generator 60C receives the multiplicand A and bits b5, b4, b3 of the multiplier B and supplies the partial product PP2, and so on. The partial product generator 60D receives the multiplicand A and bits bn-1, bn-2, bn-3 of the multiplier B and supplies the partial product PPm-1.
Booth-encoded multipliers are sometimes characterized as to its radix value (e.g., 2, 4, 8, etc.), wherein the radix value is defined by the following equation:radix value=2q-1
and where the value of q is equal to the number of multiplier bits used to generate each partial product. As to the implementation of FIG. 2, the partial product generators use three multiplier bits (i.e., bj+1, bj, bj−1) to generate the partial product, and therefore, the implementation shown in FIG. 2 is a radix 4 multiplier (radix value=2(3−1)=4). Note that for a radix 4 booth-encoded multiplier, the number of partial products (i.e. the value of m) generated by the booth-encoded partial product generator unit 22 is equal to one half the number of bits in the multiplier B, rounded up to the nearest whole number.
FIG. 3 shows a typical implementation 60 for the partial product generators 60A–60D (FIG. 2). This implementation 60 includes k partial product bit generators, four of which are shown, i.e., 70A, 70B, 70C and 70D. Note that in a radix 4 booth-encoded multiplier, the value of k is equal to the number of bits in the multiplicand A. The partial product generators 70A–70D are all identical to one another. Each partial product generator has two sets of inputs and one output. The first set of inputs is ai, ai-1. The second set of inputs is bj+1, bj, bj−1. The output is PPji. The ai, ai-1 inputs of each partial product bit generator are supplied with a group of bits of the multiplicand A. The bj+1, bj, bj−1 inputs are supplied with the signals input to the bj+1, bj, bj−1 inputs of the partial product generator 60. (The signals input to the bj+1, bj, bj−1 inputs are in some instances hereafter referred to as bits bj+1, bj, bj−1 of the multiplier B or simply multiplier bits bj+1, bj, bj−1). The PPji output of each partial product bit generator supplies one of the bits of the partial product PPj. More specifically, the partial product bit generator 70A receives bit a0 of the multiplicand A and bits bj+1, bj, bj−1 of the multiplier B, and supplies bit PPj0 of the partial product PPj. The partial product bit generator 70B receives bits a1, a0 of the multiplicand and bits bj+1, bj, bj−1 of the multiplier B, and supplies bit PPj1 of the partial product PPj, and so on. The partial product bit generator 70C receives bits an-2, an-3 of the multiplicand A and bits bj+1, bj, bj−1 of the multiplier B, and supplies bit PPjk-2 of the partial product PPj. The partial product bit generator 70D receives bits an-1, an-2 of the multiplicand A and bits bj+1, bj, bj−1 of the multiplier B, and supplies bit PPjk-1 of the partial product PPj.
FIGS. 4A and 4B show logic equations and a truth table, respectively, for each of the partial product bit generators 70A–70D (FIG. 3). The equations of FIG. 4A, which are reproduced below for the convenience of the reader, show that the logic state of the partial product bit PPji is determined as follows:PPji=(aiX1+ai-1X2)XOR N  eq. (1)whereX1=bj XOR bj−1  eq. (2)X2=NOT(bj+1)bjbj−1+bj+1NOT(bj)NOT (bj−1)  eq. (3)andN=bj+1  eq. (4).
Note that the logic state of the partial product bit PPji depends on the logic state of X1, X2, and N (where X1, X2, and N are intermediate signals), and on the logic state of the signals input to the ai, ai-1 inputs. (The signals input to the ai, ai-1 inputs are in some instances hereafter referred to as bits ai, ai-1 of the multiplicand A or simply multiplicand bits ai, ai-1). In the steady state, the logic state of X1 depends only on the logic state of two multiplier bits (i.e., bj and bj−1). The logic state of X2 depends only on the logic state of three multiplier bits (i.e., bj+1, bj, bj−1). The logic state of N depends only on the logic state of one multiplier bit (i.e., bj+1).
Referring now to FIG. 4B, the truth table has eight columns. More specifically, the table has three columns for the inputs (multiplier bits bj+1, bj, bj−1), three columns for the intermediate signals (X1, X2, N), one column for the output from the partial product bit generators (PPji), and one column for output from the partial product generator (PPj).
The table has eight rows, one for each possible combination of the multiplier bits bj+1, bj, bj−1. From the truth table, it can be seen that if the multiplier bits bj+1, bj, bj−1 have logic states 0, 0, 0 respectively, then each of the partial product bit generators outputs a 0 regardless of the logic states of the multiplicand bits ai, ai-1. (Recall that each of the partial product bit generators are supplied with the same group of multiplier bits bj+1, bj, bj−1). Consequently, the partial product PPj may be viewed as being equivalent to 0.
If the multiplier bits bj+1, bj, bj−1 have logic states 0, 0, 1, or 0, 1, 0, then each of the partial product bit generators outputs a logic state equal to that of the multiplier bit supplied to its ai input. Consequently, the partial product PPj is equivalent to the multiplicand A, i.e., A.
If the multiplier bits bj+1, bj, bj−1 have logic states 0, 1, 1, then each of the partial product bit generators outputs a logic state equal to that of the multiplier bit supplied to its ai-1 input. Consequently, the partial product PPj is equivalent to the multiplicand A multiplied by two, i.e., 2A.
If the multiplier bits bj+1, bj, bj−1 have logic states 1, 0, 0, then each of the partial product bit generators outputs a logic state equal to the inverse of the logic state of the multiplier bit supplied to its ai-1 input. Consequently, the partial product PPj is equivalent to the multiplicand A multiplied by negative two, i.e., −2A.
If the multiplier bits bj+1, bj, bj−1 have logic states 1, 0, 1, or 1, 1, 0 then each of the partial product bit generators outputs a logic state equal to the inverse of the logic state of the multiplier bit supplied to its as input. Consequently, the partial product PPj is equivalent to the multiplicand A multiplied by negative one, i.e. −A.
If the multiplier bits bj+1, bj, bj−1 have logic states 1, 1, 1, then each of the partial product bit generators outputs a 1. This results in bits PPjk-1 through PPj0 of the partial product PPj having logic states equal to 1, . . . , 1, respectively. However, the net effect of the partial product PPj to the downstream adder 24 becomes 0, . . . , 0 because a sign bit equal to 1 is added to the LSB of the partial product PPj by the compression tree in the adder. Consequently, the result is the same as if each of the partial product bit generators had actually output a 0, i.e., PPj equal to 0.
FIG. 5A shows one implementation 70 of the partial product bit generators 70A–70D. This implementation 70 has three circuits 90, 92, 94. The first circuit 90 receives the signals bj, bj−1 and generates the signal X1. The second circuit 92 receives the signals bj+1, bj, bj−1 and generates the signal X2. The third circuit 94 receives the signals ai, ai-1 and the outputs from the first and the second circuits 90, 92 and generates the partial product bit PPji.
Each of the three circuits 90, 92, 94 makes use of combinatorial logic. This combinatorial logic is to be discussed hereinbelow. First however, a definition for the term “combinatorial logic” and a basis for characterizing circuits with combinatorial logic is to be provided.
The term “combinatorial logic”, as used herein, is defined as a circuit (or a circuit portion) that receives two or more logic signals and provides one or more logic signal in response thereto. Combinatorial logic is typically used to perform a sequence (or multiple sequences) of combinatorial logic operations.
Combinatorial logic may take many forms including but not limited to logic gates(s). Examples of logic gates include AND, NAND, OR, NOR, EXCLUSIVE AND (i.e., XAND), EXCLUSIVE NAND (i.e., XNAND), EXCLUSIVE OR (i.e., XOR), EXCLUSIVE NOR (i.e., XNOR) logic gates, and combinations thereof. However, it should be understood that a conventional inverter gate, which receives only a single logic input, is not considered combinatorial logic. Logic gates may or may not employ standard logic family circuitry. Example of logic families include but are not limited to TTL, DTL, ECL, CMOS, wired logic and combinations thereof.
Other types of circuitry (i.e., non logic-gate types of circuits) to perform combinatorial logic include, but are not limited to, pass transistor arrangements and transmission gates.
Combinatorial logic circuits may be implemented in any suitable technology including but not limited to bipolar technology, CMOS technology, and combinations thereof.
Circuits (and data paths within circuits) with combinatorial logic are sometimes characterized as to their “number of levels of combinatorial logic”. The number of levels of combinatorial logic in a data path is equal to the number of basic combinatorial logic operations from the inputs of the data path to the output of the data path. Basic combinatorial logic operations are defined herein as: AND, OR, NAND, and NOR. Similarly, the number of levels of combinatorial logic in a circuit is equal to the number of basic combinatorial logic operations in the longest data path within the circuit. The longest data path within the circuit is the data path having the highest number of basic combinatorial logic operations from the inputs of the data path to the output of the data path.
Note that some logic gates, by themselves, comprise more than one level of combinatorial logic. For example, an XOR gate (which is typically implemented using the combinatorial operations X NOT (Y)+YNOT (X)), typically comprises at least two levels of combinatorial logic.
Referring again to FIG. 5A, with the above definitions in mind, it should now be recognized that the partial product bit generator shown in FIG. 5A has exactly six levels of combinatorial logic. The first circuit 90 has two levels of combinatorial logic (recall that the XOR gate is made up of two levels of combinatorial logic). The second circuit 92 has two levels of combinatorial logic (the AND gates 98, 100 make up the first level, the OR gate 104 makes up the second level), which are in parallel with the two levels in the first circuit. The third circuit 94 has four levels of combinatorial logic (the AND gates 106, 110 make up the first level, the OR gate 112 makes up the second level, and the XOR gate 118 makes up the third level). Note that in some embodiments, signals having logic states equal to the inverse of the logic states of the multiplier bits bj, bj−1 may be generated and made globally available with the partial product generator, thereby eliminating the need for the inverters 120, 122, 124 in the second circuit 92.
FIG. 5B shows another implementation 70 of the partial product bit generators 70A–70D. The implementation of FIG. 5B is similar to the implementation of FIG. 5A in that the implementation of FIG. 5B has first, second, and third logic circuits 130, 132, 134 that generate the signals X1, X2, and PPji, respectively. One difference between the implementation of FIG. 5B and the implementation of FIG. 5A is that the implementation of FIG. 5B includes a multiplexer 146. The multiplexer 146 is made up of a pass transistor arrangement (not shown) and is therefore referred to herein as a pass transistor multiplexer.
As in the implementation of FIG. 5A, the implementation of FIG. 5B has exactly six levels of combinatorial logic. In particular, the first circuit 130 has two levels of combinatorial logic (the XOR gate 136 is made up of two levels of combinatorial logic). The second circuit also has two levels of combinatorial logic (the NOR gates 142, 152 make up the first level of combinatorial logic and the multiplexer 146 makes up the second level of combinatorial logic), which are in parallel with the two level in the first circuit. The third circuit 134 has four levels of logic (the NAND gates 158, 160 make up the first level, the NAND gate 162 makes up the second level, and the XOR gate 164 makes up the third and fourth levels). Note that the inverters 138, 140 in the first circuit 130 and the inverters 166, 168 help provide drive capability. Note that in some embodiments, signals having logic states equal to the inverse of the logic states of the multiplier bits bj, bj−1 may be generated and made globally available with the partial product generator, thereby eliminating the need for the inverters 148, 150 in the second circuit 132.
Booth-encoded multipliers often require less area than multipliers that generate partial products using 2-input NAND gates. Thus the use of booth-encoded multipliers can facilitate a reduction in the size of data processors and/or help to make room to incorporate other features into data processors.
Nevertheless, enhancements in booth-encoded methods are desired. For example, it would be advantageous to increase the operational speed and/or reduce the amount of power required for booth-encoded methods. A further reduction in the area requirements would also be desirable.